home *** CD-ROM | disk | FTP | other *** search
/ Fritz: All Fritz / All Fritz.zip / All Fritz / FILES / PROGNG_C / TURBOCU2.LZH / INDEX.ARC / INDEX.DOC < prev    next >
Text File  |  1987-08-21  |  22KB  |  553 lines
  1. .PL
  2. Aå
  3.  
  4.  
  5. INDEX.DOC                   Version 1.01                   August 21, 1987
  6.                                                                    Page 1
  7.  
  8. This documentation and the software it describes are Copyright 1987, Jim 
  9. Mischel.  You are free to use this software providing that the following 
  10. conditions are met:
  11.  
  12.      1)  Any distributed versions contain the my copyright notice and are 
  13.          accompanied by documentation and source code.  The package doesn't do 
  14.          anybody any good if they don't know how to use it.
  15.      2)  You notify me before using it in any commercial application.  I won't 
  16.          ask for any money, I'd just like to know about it.  Also, if you 
  17.          notify me I may be able to get you a current version and/or notify 
  18.          you of any bug fixes.
  19.  
  20. This package was developed using Turbo C version 1.0.  It should port to other 
  21. compilers and operating systems with very little modification.
  22.  
  23. Questions, comments, problems should be addressed to Jim Mischel, CIS id 
  24. number 73717,1355.  I regularly visit BORPRO, CLMFORUM, and DDJFORUM.  I'd be 
  25. more than happy to reply to inquiries.
  26.  
  27.  
  28. INDEX.DOC                   Version 1.01                   August 21, 1987
  29.                                                                    Page 2
  30. DESCRIPTION
  31.  
  32. INDEX is a collection of routines designed to provide single-key indexed file 
  33. access to C programs.  They are modeled after the ISAM features supplied in 
  34. standard COBOL implementations, with some additions.  Keys can be of any type, 
  35. including float, double, and user-defined key types.
  36.  
  37. This version of the package uses a threaded binary tree to maintain the index.  
  38. This may change in future versions.  I chose the threaded tree because it is 
  39. relatively simple to implement, uses little memory, and is acceptable for 
  40. small and medium-sized data sets.  It is not the fastest method available, and 
  41. I make no claims as to the speed of record access, though it should be 
  42. acceptable.  Currently, no balancing is performed when adding or deleting 
  43. records from the file.  In many cases, this can result in a severely un-
  44. balanced tree and horribly slow access times.  I am currently working on 
  45. adding the tree balancing routines.
  46.  
  47. Following are descriptions of the user-accessable routines.  These are the 
  48. only routines that should be called by applications programs.  Calling other 
  49. routines in the package will produce unpredictable results and could very 
  50. possibly destroy the database.
  51.  
  52. The examples provided build on previous examples.  For example, the example 
  53. used with iclose() uses data types defined in the example provided with 
  54. iopen().
  55.  
  56.  
  57. INDEX.DOC                   Version 1.01                   August 21, 1987
  58.                                                                    Page 3
  59. IOPEN - open a file for indexed I/O
  60.  
  61. void *iopen(char *fname, unsigned recsiz, char keytyp, unsigned offset,
  62.             char dupflag, int (*cmp_rtn)());
  63.  
  64. iopen opens an indexed file for reading/writing.  If the file to be opened 
  65. does not exist, iopen attempts to create it.  Upon successful completion, 
  66. iopen will return a pointer to an index control record.  This pointer should 
  67. not be modified by the application program, nor should the fields in the index 
  68. control record be changed by the application.  The data in the record is used 
  69. by the index routines and is at best marginally useful to the application.  
  70. Modifying either the returned pointer or the data pointed to will produce 
  71. unpredictable results and could very likely make the database unuseable.  If 
  72. iopen can not open the file, NULL is returned and the global variable ierrno 
  73. is set to identify the cause of the error. 
  74.  
  75. Arguments passed to iopen()
  76.  
  77. fname          A string containing the name of the file to be opened.  This 
  78.                name should be without an extension.  iopen will append the 
  79.                extension '.DAT' for the data file and the extension '.INX' for 
  80.                the index file.
  81.  
  82. recsiz         Size of the data record in characters.
  83.  
  84. keytyp         The type of key.  Standard key types supplied in the header 
  85.                file, INDEX.H are:
  86.  
  87.                UCHAR   unsigned character key
  88.                SCHAR   signed character key
  89.                UINT    unsigned int key
  90.                SINT    signed int key
  91.                ULONG   unsigned long key
  92.                SLONG   signed long key
  93.                STRING  string key (ASCIIZ)
  94.                FLOAT   float key
  95.                DOUBLE  double key
  96.  
  97.                The last two key types (FLOAT and DOUBLE) are available only if 
  98.                INDEX.C was compiled with the FLOAT_KEY option.  This prevents 
  99.                the floating point libraries from being included unless they 
  100.                are needed.
  101.  
  102.                If the key for this file is not one of the above types, use 0 
  103.                for keytyp and pass the name of the key comparison routine in 
  104.                the cmp_rtn field.
  105.  
  106. offset         The offset (in characters) from the beginning of the record to 
  107.                the first byte of the key.
  108.  
  109. dupflag        Controls whether duplicate keys are allowed.  If dupflag is 0, 
  110.                duplicate keys are not allowed, and an attempt to add a 
  111.                duplicate key will return an error (see error codes below).  If 
  112.                dupflag is 1, duplicate keys will be allowed.
  113.  
  114.  
  115. INDEX.DOC                   Version 1.01                   August 21, 1987
  116.                                                                    Page 4
  117. IOPEN - open a file for indexed I/O
  118.  
  119. cmp_rtn        Is a pointer to a user-defined key comparison routine.  If the 
  120.                key is one of the standard key types, this field should be 
  121.                NULL.  If this field is not NULL, iopen will use this as a 
  122.                pointer to a user-defined key comparison routine.  The 
  123.                declaration of the routine should be:
  124.  
  125.                int routine_name(void *arg1, void *arg2);
  126.  
  127.                This routine accepts pointers to the operands and returns
  128.                   -1 if arg1 < arg2
  129.                    0 if arg1 == arg2
  130.                    1 if arg1 > arg2
  131.  
  132. Example:
  133.  
  134. #include <stdio.h>
  135. #include "index.h"
  136.  
  137. main (int argc, char *argv[]) {
  138.  
  139. struct {
  140.   char first_name[25],
  141.        last_name[25];
  142. } name_rec;
  143.  
  144. char *name_file;         /* pointer to control record */
  145. unsigned offset;
  146.  
  147. offset = &name_rec.last_name - &name_rec;    /* compute key offset */
  148. if ((name_file = iopen(argv[1],sizeof(name_rec),STRING,offset,1,NULL) == NULL) 
  149.   {
  150.     printf("Error opening file %s\n",argv[1]);
  151.     printf("Error code is %X\n",ierrno);
  152.     return;
  153.   }
  154.  
  155.  
  156. INDEX.DOC                   Version 1.01                   August 21, 1987
  157.                                                                    Page 5
  158. ICLOSE - close files and free memory
  159.  
  160. void iclose(void *db_control);
  161.  
  162. iclose closes the index and data files assigned to the index control record, 
  163. and frees the memory used.  iclose does not return status.
  164.  
  165. IMPORTANT NOTE:
  166. All files opened with iopen that have had records added or deleted MUST be 
  167. closed with iclose.  Failure to do so may result in losing data or destroying 
  168. the integrity of the index file.
  169.  
  170. Arguments passed to iclose()
  171.  
  172. db_control     The pointer returned when the file was opened by iopen.
  173.  
  174.  
  175. Example: (building on the one above)
  176.  
  177.   iclose(name_file);
  178.  
  179.  
  180. INDEX.DOC                   Version 1.01                   August 21, 1987
  181.                                                                    Page 6
  182. IREAD - read a record from the file
  183.  
  184. int iread(void *db_control, void *destin);
  185.  
  186. iread reads a record and places it in memory at destin.  iread assumes there 
  187. is sufficient space at destin to hold the entire data record.  Place the key 
  188. value to be searched for at the key position in the record at destin and call 
  189. iread.  iread returns 0 if the record was found, I_NOREC if not, and error 
  190. status if there was an I/O error.  On error conditions, the data at destin is 
  191. not changed.  Using iread does not change the pointer used by the sequential 
  192. read functions iread_next and iread_prev.
  193.  
  194. Arguments passed to iread()
  195.  
  196. db_control     The pointer returned when the file was opened by iopen.
  197.  
  198. destin         A pointer to the structure that will receive the data record.
  199.  
  200. Example:
  201.  
  202.   name_rec.last_name = "Mischel";
  203.   if (iread(name_file,&name_rec)) {
  204.     printf("\007Record key %s not found in file %s\n",
  205.             name_rec.last_name,argv[1]);
  206.     printf("Error code is %X\n",ierrno);
  207.   }
  208.   else
  209.     printf("Record found\n");
  210.  
  211.  
  212. INDEX.DOC                   Version 1.01                   August 21, 1987
  213.                                                                    Page 7
  214. ISTART - position file for sequential access
  215.  
  216. int istart(void *db_control, char cond, void *source);
  217.  
  218. istart positions the file pointer for sequential file access.  This function 
  219. must be called before attempting to sequentially access the file through 
  220. iread_next or iread_prev.  Place the key value to be searched for at the key 
  221. position in source and call istart.  No data is transferred by this function.
  222. istart will return 0 if the file pointer was positioned successfully, EOF if 
  223. no record meeting key and cond could be found, and one of the standard error 
  224. codes on error.
  225.  
  226. Arguments passed to istart()
  227.  
  228. db_control     The pointer returned when the file was opened by iopen.
  229.  
  230. cond           One of the conditions defined in INDEX.H:
  231.  
  232.                START_FILE     Start at beginning of file, source is ignored
  233.                LT             Start at the key less than the key in source
  234.                LE             Start at key less then or equal to key in 
  235.                               source.  If a record exists with key, it will 
  236.                               start there.
  237.                EQ             Start at key equal to the key in source.
  238.                GE             Start at key greater than or equal to key in 
  239.                               source.  If a record exists with key, it will 
  240.                               start there.
  241.                GT             Start at key greater than key in source.
  242.                END_FILE       Start at end of file.  This is useful for 
  243.                               reading the entire file backwards.
  244.  
  245. Example:
  246.  
  247. /*
  248.  * to position the file at the first record with a key greater than or equal
  249.  * to Sm.
  250.  */
  251.   name_rec.last_name = "Sm";
  252.   if (istart(db_control,GE,&name_rec)) {
  253.     printf("Couldn't position file\n");
  254.     printf("Error code is %X\n",ierrno);
  255.   }
  256.   else {
  257.   /*
  258.    * read the file sequentially forward or backward.  See examples for
  259.    * iread_next and iread_prev.
  260.    */
  261.   }
  262.  
  263.  
  264. INDEX.DOC                   Version 1.01                   August 21, 1987
  265.                                                                    Page 8
  266. IREAD_NEXT - Sequentially read the next record
  267.  
  268. int iread_next(void *db_control, void *destin);
  269.  
  270. Read the next record in sequence into destin.  iread_next assumes there is 
  271. room in destin for the entire record.  Returns 0 if successful, EOF at end of 
  272. file, standard error code on error.  On error conditions, the data at destin 
  273. is not changed.
  274.  
  275. Arguments passed to iread_next()
  276.  
  277. db_control     The pointer returned when the file was opened by iopen.
  278.  
  279. destin         A pointer to the structure to receive the data record.
  280.  
  281. Example:
  282.  
  283.   /*
  284.    * read the file sequentially forward (assuming it was started as above)
  285.    */
  286.     while (!iread_next(db_control,&name_rec))
  287.       printf("%s %s\n",name_rec.first_name,name_rec.last_name);
  288.  
  289.  
  290. INDEX.DOC                   Version 1.01                   August 21, 1987
  291.                                                                    Page 9
  292. IREAD_PREV - sequentially read the previous record
  293.  
  294. int iread_prev(void *db_control, void *destin);
  295.  
  296. read the previous record in sequence into destin.  Assumes there is room in 
  297. destin for the entire record.  Returns 0 if successful, EOF at top of file, 
  298. standard error code on error.  On error conditions, the data at destin is not 
  299. changed.
  300.  
  301. Arguments passed to iread_prev()
  302.  
  303. db_control     The pointer returned when the file was opened by iopen.
  304.  
  305. destin         A pointer to the structure to receive the data record.
  306.  
  307. Example:
  308.  
  309.   /*
  310.    * read the file sequentially backward (assuming it was started as above)
  311.    */
  312.     while (!iread_prev(db_control,&name_rec))
  313.       printf("%s %s\n",name_rec.first_name,name_rec.last_name);
  314.  
  315.  
  316. INDEX.DOC                   Version 1.01                   August 21, 1987
  317.                                                                    Page 10
  318. IWRITE - add a new record
  319.  
  320. int iwrite(void *db_control, void *source);
  321.  
  322. Write the record from source to the data file.  Data records are always added 
  323. to the end of the file.  Returns 0 if successful, I_INVKEY if duplicates are 
  324. not permitted and an attempt was made to add a duplicate record, standard 
  325. error code otherwise.
  326.  
  327. Arguments passed to iwrite()
  328.  
  329. db_control     The pointer returned when the file was opened by iopen.
  330.  
  331. source         A pointer to the structure to be written.
  332.  
  333. Example:
  334.  
  335.   name_rec.first_name = "Jim";
  336.   name_rec.last_name = "Mischel";
  337.   switch (iwrite(db_control,&name_rec)) {
  338.     case 0        :
  339.       printf("Record written\n");
  340.       break;
  341.     case I_INVKEY :
  342.       printf("Duplicate key %s\n",name_rec.last_name);
  343.       break;
  344.     default       :
  345.       printf("Write error.  Error code is %X\n",ierrno);
  346.   }
  347.  
  348.  
  349. INDEX.DOC                   Version 1.01                   August 21, 1987
  350.                                                                    Page 11
  351. IREWRITE - update an existing record
  352.  
  353. int irewrite(void *db_control, void *source);
  354.  
  355. Update the current record in the file.  The record must have been read using 
  356. one of the read routines, or written using iwrite, and must still be in the 
  357. buffer.  It is not possible to change the key using irewrite.  Use idelete to 
  358. remove the record and iwrite to add the record after the key has been changed.
  359. Returns 0 on success, I_INVKEY if attempt to rewrite a record that isn't in 
  360. the buffer, standard error code otherwise.
  361.  
  362. Arguments passed to irewrite()
  363.  
  364. db_control     The pointer returned when the file was opened by iopen.
  365.  
  366. source         A pointer to the structure to be written.
  367.  
  368. Example:
  369.  
  370.   /* first we have to read the record */
  371.   name_rec.last_name = "Smith";
  372.   if (iread(name_file,&name_rec)) {
  373.     printf("\007Record key %s not found in file %s\n",
  374.             name_rec.last_name,argv[1]);
  375.     printf("Error code is %X\n",ierrno);
  376.   }
  377.   else {
  378.     name_rec.first_name = "John";
  379.     switch (irewrite(db_control,&name_rec)) {
  380.       case 0 :
  381.         printf("Success\n");
  382.         break;
  383.       case I_INVKEY :
  384.         printf("Invalid rewrite attempted\n");
  385.         break;
  386.       default :
  387.         printf("Rewrite error.  Error code is %X\n",ierrno);
  388.     }
  389.  
  390.  
  391. INDEX.DOC                   Version 1.01                   August 21, 1987
  392.                                                                    Page 12
  393. IDELETE - delete a record
  394.  
  395. int idelete(void *d, void *source);
  396.  
  397. Delete the record currently in the buffer.  Record must have been read using 
  398. one of the read routines, or written using iwrite, and still be in the buffer.  
  399. Returns 0 on success, I_INVKEY if attempt to delete a record that isn't in the 
  400. buffer, standard error code otherwise.
  401.  
  402. When a record is deleted, it is not removed from the data file and its index 
  403. pointer is not removed from the index file.  What happens is that the index 
  404. pointers are re-arranged to point past the deleted record.  This has at least 
  405. two major side affects:
  406.   1)  If the data file is scanned by a program that doesn't use the index 
  407.       routines, deleted records will be picked up along with current records.
  408.   2)  In a file that has a large turnover rate, there will be a considerable 
  409.       amount of wasted space taken up by the deleted records.
  410. The next version of the package will include a rebuild() function that will, 
  411. among other things, remove deleted records from a data file.  This program 
  412. will fix the second problem.  The first problem can be solved in one of two 
  413. ways:
  414.   1)  Add a flag to the data record to indicate it is deleted.  Your program 
  415.       will have to manipulate this flag, setting it before the record is 
  416.       deleted.
  417.   2)  Wait for the next version of the package.  By using the rebuild() 
  418.       function before scanning the file, you're guaranteed not to have any 
  419.       deleted records.
  420.  
  421. Arguments passed to idelete()
  422.  
  423. db_control     The pointer returned when the file was opened by iopen.
  424.  
  425. source         A pointer to the structure containing the key name to be 
  426.                deleted.
  427.  
  428.  
  429. INDEX.DOC                   Version 1.01                   August 21, 1987
  430.                                                                    Page 13
  431. IDELETE - delete a record
  432.  
  433. Example:
  434.  
  435.   /* first read the record */
  436.   name_rec.last_name = "Smith";
  437.   if (iread(name_file,&name_rec)) {
  438.     printf("\007Record key %s not found in file %s\n",
  439.             name_rec.last_name,argv[1]);
  440.     printf("Error code is %X\n",ierrno);
  441.   }
  442.   else {
  443.     switch (idelete(db_control,&name_rec)) {
  444.       case 0 :
  445.         printf("Record deleted\n");
  446.         break;
  447.       case I_INVKEY :
  448.         printf("Invalid delete attempted\n");
  449.         break;
  450.       default :
  451.         printf("Delete error.  Error code is %X\n",ierrno);
  452.     }
  453.  
  454.  
  455. INDEX.DOC                   Version 1.01                   August 21, 1987
  456.                                                                    Page 14
  457. ERROR CODES
  458.  
  459. The global variable ierrno will contain the results of the last I/O operation.  
  460. Possible values are:
  461.  
  462. Code      Value  Description
  463. ----      -----  -----------
  464. I_NODAT   0x10 - couldn't open data file (iopen)
  465. I_DATRD   0x11 - I/O error attempting to read data file (any)
  466. I_DATWT   0x12 - I/O error attempting to write to data file (any)
  467. I_NOINX   0x20 - couldn't open index file (iopen)
  468. I_INXRD   0x21 - I/O error attempting to read index file (any)
  469. I_INXWT   0x22 - I/O error attempting to write to index file (any)
  470. I_INVKEY  0x80 - Attempt to add duplicate key (iwrite)
  471.                  Attempt to rewrite deleted record, or record not in buffer
  472.                  (irewrite)
  473.                  Attempt to delete deleted record, or record not in buffer
  474.                  (idelete)
  475. I_NOMEM   0x81 - out of memory (iopen)
  476. I_NOREC   0x82 - record not found (iread)
  477.  
  478.  
  479. INDEX.DOC                   Version 1.01                   August 21, 1987
  480.                                                                    Page 15
  481. NOTES
  482.  
  483. I have included a sample program that illustrates the use of several of the 
  484. routines in this package.  The program, ADR.C, is a simple address/phone book 
  485. that is marginally useful as a real application, but does show how to use the 
  486. routines.
  487.  
  488. MAKE FILE
  489. I have included a make file that can be used to re-compile the package.  This 
  490. file uses the QLIB program to create the library INDEX.LIB.  The QLIB program 
  491. is available on BORPRO DL 11.  The library supplied with the package is a 
  492. TLINK compatible library and is not compatible with Microsoft's LINK.  
  493.  
  494. KNOWN BUGS
  495.  
  496. There are some possible conflicts when using sequential and random I/O at the 
  497. same time.  These will only occur when adding or deleting records while 
  498. sequentially scanning the file.  In general, the only problems involve 
  499. deleting a record that is to be the next one read, or adding a record between 
  500. the current and next records.  In the delete case, the deleted record will 
  501. still be read, and in the add case, the new record will not be read.  The next 
  502. release should fix these problems.
  503.  
  504. REVISION HISTORY
  505.  
  506. This package started as a "I wonder how that's done" type of project.  The 
  507. original program used a primitive hashing algorithm to store and retrieve the 
  508. keys.  The program (written in Pascal) did work, but was a terrible kludge and 
  509. I threw it away.  The current version was written for two reasons:  1)  I 
  510. wanted to learn C, and 2)  I needed something like this for a project I was 
  511. planning.
  512.  
  513. Version 1.00  August 13, 1987
  514. Original release version.
  515.  
  516. Version 1.01  August 21, 1987
  517.      1) Fixed bugs in iwrite() and irewrite() that prevented the data buffer 
  518.         from being updated when the record was written.  This bug caused 
  519.         irewrite() and idelete() to erroneously return I_INVKEY.
  520.      2) Updated documentation.  Added examples and cleaned things up quite a 
  521.         bit.
  522.      3) Split the package into multiple source files and added a make file 
  523.         that creates a Turbo C compatible library.
  524.      4) Add calls to fflush() in the write routines.  This slows things down a 
  525.         bit (a lot?), but does help keep data file integrity.
  526.  
  527.  
  528. INDEX.DOC                   Version 1.01                   August 21, 1987
  529.                                                                    Page 16
  530. NOTES
  531.  
  532. Files that make up the index package
  533.  
  534. ADR.C     - demonstration program for index package
  535. ADR.MAK   - make file for ADR
  536. ADR.PRJ   - project file for ADR
  537. ARCIT.BAT - batch file to build the archive
  538. IDELETE.C - delete record routine
  539. INAMES    - name file for QLIB program
  540. INXRTNS.C - support functions for index package
  541. INDEX.DOC - index documentation, rough but useable
  542. INDEX.H   - header file included by application programs
  543. INDEX.LIB - index routines library (useable only by TLINK, not by MS LINK)
  544. INDEX.MAK - make file for index routines
  545. INXDEFS.H - header file for index routines
  546. IOPEN.C   - open and close functions
  547. IREADN.C  - readnext function
  548. IREADP.C  - readprevious function
  549. IREADR.C  - read random function
  550. IREWRITE.C- rewrite (update) record function
  551. ISTART.C  - start function
  552. IWRITE.C  - write record function
  553. Aî